
class Mergesort():

	# p - posicao inicial = 1
	# q - posicao mediana
	# r - tamanho da lista
	def __init__(self,lista,p,r):
		self.lista = lista
		self.primeiroIndice = p
		self.listaTamanho = r
		self.merge_sort(self.lista,self.primeiroIndice,self.listaTamanho)
	
	def merge_sort(self,A, p, r):
		if p < r:
			q = (p + r ) / 2
			self.merge_sort(A, p, q)
			self.merge_sort(A, q+1, r)
			self.mergee(A, p, q, r)
			#print 'QQQQQQQ : ', q


	def mergee(self, A, p, q, r):
		
		n1 = q - p + 1
		n2 = r - q

		listaLeft=[]
		listaRight=[]

		for i in range(n1):
			#print 'lista Left : ', A[p+i-1]
			listaLeft.append(A[p+i-1])

		for j in range(n2):
			#print 'lista Right : ', A[q+j]
			listaRight.append(A[q+j])

		listaLeft.append(9999)
		listaRight.append(9999)
		#print 'LEN  1 : ', len(listaLeft)
		#print 'Len 2 : ', len(listaRight)
		i=0
		j=0
		
		for k in range(p-1,r):
			#k=p
			if listaLeft[i] <= listaRight[j]:
				A[k] = listaLeft[i]
				#print listaLeft[i]
				i=i+1
			else:
				A[k] = listaRight[j]
				j=j+1
			

		#print 'L ',len(listaLeft)
		#print 'R ',len(listaRight)
	
	#A=[5,2,4,7,1,3,2,6]
	#merge_sort(A, 1, len(A))
	#print A


if __name__ == "__main__":
	lista=[8,3,2,9,7,1,5,4]
	print 'Mergesort Lista : ', lista
	mergesortObject = Mergesort(lista, 1, len(lista))
	print 'Lista Ordenada : ', lista